package leetcode.median;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * ClassName: $40_CombinationSum2
 * Description:
 * date: 2022-02-17 22:01
 *
 * @author liyifan
 */
public class $40_CombinationSum2 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] vis;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        vis = new boolean[candidates.length];
        Arrays.sort(candidates);
        backtrack(target, candidates, 0);
        return res;
    }

    public void backtrack(int target, int[] candidates, int index){
        if (target == 0) {res.add(new ArrayList<>(path));return;}

        for (int i = index;i < candidates.length;i++) {
            if (vis[i]){continue;}

            if (i - 1 >= index && candidates[i - 1] == candidates[i]){continue;}

            if (target > candidates[i]){
                path.add(candidates[i]);
                vis[i] = true;
                backtrack(target - candidates[i], candidates, i + 1);
                path.remove(path.size() - 1);
                vis[i] = false;
            }
        }
    }
}
